package com.zjj.algorithm.learning.atguigu.algorithm;

import java.util.Arrays;

/**
 * KMP 算法匹配
 *
 * @author zjj_admin
 * @date 2022/12/31 10:56
 */
public class KmpMatch {

    public static void main(String[] args) {
        String str1 = "BBC ABCDAB ABCDABCDABDE";
        String str2 = "ABCDABD";
//        String str2 = "BBC";

        int[] next = kmpNext("AAAB");
        System.out.println("next = " + Arrays.toString(next));

        int index = kmpMatch(str1, str2);
        System.out.println("index = " + index);
    }


    /**
     * KMP 匹配算法
     *
     * @param str1 匹配源字符串
     * @param str2 匹配子串
     * @return
     */
    public static int kmpMatch(String str1, String str2) {
        //获取子串的部分匹配表
        int[] next = kmpNext(str2);

        for (int i = 0, j = 0; i < str1.length(); i++) {

            char c1 = str1.charAt(i);
            char c2 = str2.charAt(j);
            //KMP 算法的核心点
            while (j > 0 && c1 != c2) {
                j = next[j - 1];
                c2 = str2.charAt(j);
            }

            if (c1 == c2) {
                j++;
            }
            if (j == str2.length()) {
                return i - j + 1;
            }
        }
        return -1;
    }


    /**
     * 获取子串的部分匹配表
     *
     * @param dest
     * @return
     */
    public static int[] kmpNext(String dest) {
        int[] next = new int[dest.length()];
        next[0] = 0;
        for (int i = 1, j = 0; i < dest.length(); i++) {

            //这里时 KMP 算法的核心
            while (j > 0 && dest.charAt(i) != dest.charAt(j)) {
                j = next[j - 1];
            }

            //当满足 dest.charAt(i) == dest.charAt(j) 时，部分匹配值就需要 + 1
            if (dest.charAt(i) == dest.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
        return next;
    }
}
